﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Demo.Framework.Algorithms.UnionFind
{
    /*Aim - To determine if two objects are connected in a network
     * We can use the Quick Union algorithm to compress the path (instead of balancing the tree)
     * Just after computing the root set the id of each examined node (parents) to the root
     * */
    class PathCompression
    {
        private int[] _array;
        private int[] _size;
        private int _count;

        public PathCompression(int N)
        {
            _count = N;
            _array = new int[N];

            for (int i = 0; i < _count; i++)
            {
                _array[i] = i;
            }            
        }

        public bool IsConnected(int p, int q)
        {
            return Root(p) == Root(q);
        }

        public bool Union(int p, int q)
        {
            try
            {
                int root_p = Root(p);
                int root_q = Root(q);
                if (_size[p] <= _size[q])
                {
                    _array[root_p] = root_q;
                    _size[q] = _size[q] + 1;
                }
                else
                {
                    _array[root_q] = root_p;
                    _size[p] = _size[p] + 1;
                }
                _array[root_p] = root_q;
                return true;
            }
            catch (Exception)
            {                
                return false;
            }
        }

        private int Root(int i)
        {            
            while (i != _array[i])
            {
                // Make every other node point to its grand parent - halving the length
                _array[i] = _array[_array[i]];
                i = _array[i];
            }
            return i;
        }
    }
}
